package com.example.lcpractice.heading_offer;

import com.example.lcpractice.datastructure.ListNode;

/**
 * [剑指 Offer 43]1～n 整数中 1 出现的次数.java
 * 输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
 *
 * 例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
 *
 * 示例 1：
 *
 * 输入：n = 12
 * 输出：5
 * 示例 2：
 *
 * 输入：n = 13
 * 输出：6
 * 限制：
 *
 * 1 <= n < 2^31
 */
public class q43 {
    public static void main(String[] args) {
        System.out.println(countDigitOne(13));
    }

    /**
     * 时间复杂度爆表
     * @param n
     * @return
     */
    public static int countDigitOne(int n) {
        int count = 0;
        for (int i = 1; i <=n; i++) {
            String tempNum=""+i;
            if (tempNum.contains("1")) {
                String temp2 = tempNum.replaceAll("1", "");
                count += tempNum.length() -temp2.length();
            }
        }
        return count;
    }
}
